package com.hqq.exercise.array;

import java.util.Arrays;

/**
 * GetLeastNumber 最小的k个数
 * 题目描述:
 * 输入n个整数，找出其中最小的k个数
 * 样例输入
 * {4,5,1,6,2,7,3,8},4
 * 样例输出
 * 1,2,3,4.
 * 思路:
 * 1.选择排序 第n次排序的结果是第n小的数
 * 2.最大堆 堆排序
 * 3.快排
 * Created by heqianqian on 2017/8/17.
 */
public class GetLeastNumber {

    /**
     * 思路:
     * 根据选择排序第n趟结果是第n大[小]的元素
     */
    public static int[] getLeastNumberBySelectSort(int[] array, int n) {
        if (array == null || array.length == 0 || n < 0 || n > array.length) {
            return null;
        }
        int index = 0;
        int min;
        for (int i = 0; i < n; i++) {
            min = array[i + 1];
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < min) {
                    min = array[j];
                    index = j;
                }
            }
            if (min < array[i]) {
                int temp = array[i];
                array[i] = array[index];
                array[index] = temp;
            }
        }
        return Arrays.copyOf(array, n);
    }

    /**
     * 基于快排
     */
    public static int[] getLeastNumberByQuickSort(int[] array, int n) {
        if (array == null || array.length == 0 || n < 0 || n > array.length) {
            return null;
        }
        int start = 0;
        int end = array.length - 1;
        int result = partition(array, start, end);
        while (result != n - 1) {
            if (result > n - 1) {
                end = result - 1;
                result = partition(array, start, end);
            } else {
                start = result + 1;
                result = partition(array, start, end);
            }
        }
        return Arrays.copyOf(array, n);
    }

    private static int partition(int[] array, int start, int end) {
        if (start >= end) {
            return -1;
        }
        int base = array[start];
        int leftIndex = start;
        int rightIndex = end;
        while (leftIndex != rightIndex) {
            while (leftIndex < rightIndex && array[rightIndex] >= base) {
                rightIndex--;
            }
            while (leftIndex < rightIndex && array[leftIndex] <= base) {
                leftIndex++;
            }
            if (leftIndex < rightIndex) {
                int temp = array[leftIndex];
                array[leftIndex] = array[rightIndex];
                array[rightIndex] = temp;
            }
        }

        array[start] = array[leftIndex];
        array[leftIndex] = base;

        return leftIndex;
    }

    public static void main(String[] args) {
        int[] array = new int[]{4, 5, 1, 6, 2, 7, 3, 8};
        int[] leastNumberByHeapSort = getLeastNumberByHeapSort(array, 3);
        System.out.println(Arrays.toString(leastNumberByHeapSort));
        System.out.println(leastNumberByHeapSort[0]);
    }


    /**
     * 基于堆排序
     */
    public static int[] getLeastNumberByHeapSort(int[] array, int n) {
        if (array == null || array.length == 0 || n < 0 || n > array.length) {
            return null;
        }
        initMaxHeap(array);
        int temp;
        //只需调整n次即可
        for (int i = array.length - 1; i >= array.length - n; i--) {
            temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            createMaxHeap(array, i, 0);
        }
        return Arrays.copyOf(array, n);
    }

    /**
     * 初始化最大堆
     *
     * @param array
     */
    private static void initMaxHeap(int[] array) {
        for (int i = (array.length - 1) / 2; i >= 0; i--) {
            createMaxHeap(array, array.length, i);
        }
    }

    /**
     * 调整为最大堆
     */
    private static void createMaxHeap(int[] array, int length, int index) {
        int rootIndex = index;
        int childIndex = 2 * index + 1;

        int temp = array[rootIndex];
        boolean flag = true;

        while (childIndex < length && flag) {
            if (childIndex < length - 1 && array[childIndex] < array[childIndex + 1]) {
                childIndex++;
            }
            if (temp >= array[childIndex]) {
                flag = false;
            } else {
                array[rootIndex] = array[childIndex];
                rootIndex = childIndex;
                childIndex = 2 * rootIndex + 1;
            }
        }
        array[rootIndex] = temp;
    }

}
